package com.zlk.algorithm.huawei.leetcode.dp;

import org.junit.Test;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @program: algorithm
 * @ClassName Code48_wordBreak
 * @description:单词拆分
 * 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。
 * 如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
 * 注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
 * 示例 1：
 *
 * 输入: s = "leetcode", wordDict = ["leet", "code"]
 * 输出: true
 * 解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
 * 示例 2：
 *
 * 输入: s = "applepenapple", wordDict = ["apple", "pen"]
 * 输出: true
 * 解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
 *      注意，你可以重复使用字典中的单词。
 * 示例 3：
 *
 * 输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
 * 输出: false
 * @author: slfang todo
 * @create: 2025-01-15 14:48
 * @Version 1.0
 **/
public class Code48_wordBreak {

    @Test
    public void test(){
        List<String> wordDict = new ArrayList<>();
        wordDict.add("car");
        wordDict.add("ca");
        wordDict.add("rs");
        wordBreak("cars",wordDict);
    }

//我们定义 dp[i] 表示字符串 s 前 i 个字符组成的字符串 s[0..i−1] 是否能被空格拆分成若干个字典中出现的单词
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordDictSet = new HashSet(wordDict);
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && wordDictSet.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
    public boolean wordBreakError2(String s, List<String> wordDict) {
        int n = wordDict.size();
        int[] countShows = new int[n];
        for (int i = 0; i < wordDict.size(); i++) {
            String subStr = wordDict.get(i);
            int count = countOccurrences(s, subStr);
            countShows[i]=count;
        }
        // dp[i][j] 0到i范围上
        //


        return s.length()==0;
    }

    public int countOccurrences(String original, String subStr) {
        int count = 0;
        int index = original.indexOf(subStr);

        // 如果找到了子字符串，计数加一，并继续查找剩余的字符串
        while (index != -1) {
            count++;
            index = original.indexOf(subStr, index + subStr.length());
        }
        return count;
    }

    @Test
    public void test2(){
        String mainString = "This is a test string. This is a test string.";
        String subString = "This";
        int occurrences = countOccurrences(mainString, subString);
        System.out.println("Substring occurs " + occurrences + " times.");
    }

    //完全背包
    //dp[i][j]  0到i范围，选取的
    // dp[i][j]  不要 dp[i-1][j]
    //           要  dp[i][j-str[i]]
    //     ||
    public boolean wordBreakError(String s, List<String> wordDict) {
        int m = s.length();
        int n = wordDict.size();
        boolean[][] dp = new boolean[n+1][m+1];
        for (int i = 0; i <= n; i++) {
            dp[i][0]= true;
        }
        for (int i = 1; i <= n; i++) {
            String cur = wordDict.get(i-1);
            int len = cur.length();
            for (int j = 1; j <= m; j++) {
                dp[i][j] = dp[i-1][j];
                if(j-len>=0){
                    dp[i][j] = dp[i][j]||(dp[i][j-len]&&s.substring(j-len,j).equals(cur));
                }
            }
        }
        return dp[n][m];
    }
}
